import java.util.ArrayList;
import java.util.List;

/**
 * @author : xwj
 * @date : 2021/9/14 21:10
 * @description : 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *                有效括号组合需满足：左括号必须以正确的顺序闭合。
 * @class : test22
 **/

public class test22 {

    // 1. 1 ms	38 MB
    //递归
    public static List<String> generateParenthesis1(int n) {
        List<String> res = new ArrayList<>();
        func(res, n, n, "");
        return res;
    }

    //DFS
    public static void func(List<String> res, int left, int right, String s) {
        //如果左右括号都用完了就将结果存入列表中
        if (left == 0 && right == 0) {
            res.add(s);
        }
        //如果左括号或者右括号的剩余数少于0，左括号剩余数大于右括号，说明该结果不正确，直接退出
        if (left < 0 || right < 0 || left > right) {
            return;
        }
        //添加左括号
        func(res, left - 1, right, s + "(");
        //添加右括号
        func(res, left, right - 1, s + ")");
    }

    public static void main(String[] args) {
        int n = 3;
        List<String> r = generateParenthesis1(n);
        System.out.println(r);
    }

}
